package com.LeetCode.BackTrace;

import org.junit.Test;

/**
 * 九宫格数量的手势数量
 */
public class CountOfPattern {
    private boolean[] used = new boolean[10];


    //最少 m 个点 最多 n 个点
    public int numberOfPatterns(int m, int n) {
        int res = 0;
        for(int len = m; len <= n; len ++){
            res += dfs(-1, len);
        }
        return res;
    }

    private int dfs(int last, int len){
        if(len == 0)
            return 1;
        int sum = 0;
        for(int i = 0; i<9; i++){
            if(isVaild(i,last)){
                used[i] = true;
                sum += dfs(i,len-1);
                used[i] = false;
            }
        }
        return sum;
    }

    /**
     * 0 1 2
     * 3 4 5
     * 6 7 8
     */
    public boolean isVaild(int index, int last){
        //先保证吗没有用过
        if(used[index]){
            return false;
        }

        //初始化的时候
        if(last == -1){
            return true;
        }

        //相加为奇数，说明要么相邻，要么走马步
        if((index + last) % 2 == 1)
            return true;


        int mid = (index + last) / 2;
        //跨过了中间，那么就要看看中间用过没有
        if(mid == 4)
            return used[mid];

        //不是同一列，也不是同一行
        if((index%3 != last%3) && (index/3 != last/3)){
            return true;
        }

        //跨过其他中间点，例如 1 3 5 7
        return used[mid];
    }

    @Test
    public void test(){
        System.out.println(numberOfPatterns(1,1));
    }
}
